package com.base.heap;

import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * TODO(1705. 吃苹果的最大数目)
 * 有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。在第 i 天，树上会长出 apples[i] 个苹果，这些苹果将会在 days[i] 天后（也就是说，第 i + days[i] 天时）腐烂，变得无法食用。也可能有那么几天，树上不会长出新的苹果，此时用 apples[i] == 0 且 days[i] == 0 表示。
 *
 * 你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这 n 天之后继续吃苹果。
 *
 * 给你两个长度为 n 的整数数组 days 和 apples ，返回你可以吃掉的苹果的最大数目。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-number-of-eaten-apples
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author leon
 * @date 2021年12月24日 12:31
 */
public class EatenApples {
    public int eatenApples(int[] apples, int[] days) {
        // 0位保存苹果数量，1位保存过期时间（这样我们只需要比较过去时间和当前时间即可，不需要给每个元素的保存时间减一）
        Queue<int[]> heap = new PriorityQueue<>((o1,o2) -> o1[1] - o2[1]);
        int n  = apples.length;
        int ans = 0;
        int i = 0;
        for (; i < n; i++) {
            // 保证堆里面的元素都是合法的,题目要求的只有苹果为0是，day才可能是0
            if(apples[i]>0){
                heap.add(new int[]{apples[i],days[i]+i});
            }
            ans+=eatApple(heap,i);
        }

        while (!heap.isEmpty()){
            ans+=eatApple(heap,i);
            i++;
        }
        return ans;
    }

    /**

     * 吃苹果,1表示吃了一个苹果，0表示没有吃
     * @param heap
     * @return
     */
    public int eatApple(Queue<int[]> heap,int now){

        Iterator<int[]> iterator = heap.iterator();
        while (!heap.isEmpty()){
            // 吃苹果前，将过期苹果，或者没有苹果的位置排出去
            while (heap.peek()!=null&&(heap.peek()[0]<1||heap.peek()[1]<=now)){
                heap.poll();
            }
            if(heap.peek()!=null){
                heap.peek()[0]--;
                return 1;
            }
        }

        return 0;

    }

    public static void main(String[] args) {
        System.out.println(new EatenApples().eatenApples(new int[]{1,2,3,5,2},new int[]{3,2,1,4,2}));
    }
}
